<?php

/**
 * 二叉树
 */
class BiTree {
    public $data;
    public $lChild;
    public $rChild;
}

// 建立二叉树
function CreateBiTree($arr, $i) {
    if (!isset($arr[$i])) {
        return null;
    }
    $t = new BiTree();
    $t->data = $arr[$i];
    $t->lChild = CreateBiTree($arr, $i * 2);
    $t->rChild = CreateBiTree($arr, $i * 2 + 1);
    return $t;
}

/*
      1
     / \
    2   3
   / \   \
  4   5   6

 */
$treeList = ['', '1', '2', '3', '4', '5', '', '6'];  //注意 5和6中间有空位,因为6是3的右子树
$tree = CreateBiTree($treeList, 1);
print_r($tree);
/*
BiTree Object
(
    [data] => 1
    [lChild] => BiTree Object
        (
            [data] => 2
            [lChild] => BiTree Object
                (
                    [data] => 4
                    [lChild] =>
                    [rChild] =>
                )

            [rChild] => BiTree Object
                (
                    [data] => 5
                    [lChild] =>
                    [rChild] =>
                )

        )

    [rChild] => BiTree Object
        (
            [data] => 3
            [lChild] => BiTree Object
                (
                    [data] =>
                    [lChild] =>
                    [rChild] =>
                )

            [rChild] => BiTree Object
                (
                    [data] => 6
                    [lChild] =>
                    [rChild] =>
                )

        )

)
*/

echo '==========================', PHP_EOL;

/**
 * 前序遍历(栈操作): 先打印根节点，然后再打印左子树，最后打印右子树。
 * preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)
 */
function PreOrderTraverse(?BiTree $t) {
    if ($t) {
        echo $t->data, ' ';
        PreOrderTraverse($t->lChild);
        PreOrderTraverse($t->rChild);
    }
}

echo PHP_EOL . "前序遍历: ";
PreOrderTraverse($tree);
// 1 2 4 5 3  6


/**
 * 中序遍历(栈操作): 先打印左子树，再打印根节点，最后打印右子树。
 * inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)
 */
function InOrderTraverse(?BiTree $t) {
    if ($t) {
        InOrderTraverse($t->lChild);
        echo $t->data, ' ';
        InOrderTraverse($t->rChild);
    }
}

echo PHP_EOL . "中序遍历: ";
InOrderTraverse($tree);
// 4 2 5 1  3 6


/**
 * 后序遍历(栈操作): 先打印左子树，再打印右子树，最后打印根节点。
 * postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r
 */
function PostOrderTraverse(?BiTree $t) {
    if ($t) {
        PostOrderTraverse($t->lChild);
        PostOrderTraverse($t->rChild);
        echo $t->data, ' ';
    }
}

echo PHP_EOL . "后序遍历: ";
PostOrderTraverse($tree);
// 4 5 2  6 3 1


/**
 * 层序遍历(队列操作): 遇到一个结点就入队，然后判断是否有子结点，然后把子结点入队。每遍历一个结点，就把队首的结点出队，这样就完成了按树的层次遍历。
 */
$q = InitLinkQueue();
function LevelOrderTraverse(?BiTree $t) {
    global $q;
    if (!$t) {
        return;
    }

    EnLinkQueue($q, $t);
    $node = $q;
    while ($node) {
        $node = DeLinkQueue($q);
        if ($node->lChild) {
            EnLinkQueue($q, $node->lChild);
        }
        if ($node->rChild) {
            EnLinkQueue($q, $node->rChild);
        }
        echo $node->data, ' ';
    }
}

echo PHP_EOL . "层序遍历: ";
LevelOrderTraverse($tree);
echo PHP_EOL;
// 1 2 3 4 5  6

// 链式队列相关代码(code08_LinkQueue.php)
class LinkQueueNode {
    public $data;
    public $next;
}

class LinkQueue {
    public $first; // 队头指针
    public $rear; // 队尾指针
}

function InitLinkQueue() {
    $node = new LinkQueueNode();
    $node->next = null;
    $queue = new LinkQueue();
    $queue->first = $node;
    $queue->rear = $node;
    return $queue;
}

function EnLinkQueue(LinkQueue &$queue, $e) {
    $node = new LinkQueueNode();
    $node->data = $e;
    $node->next = null;

    $queue->rear->next = $node;
    $queue->rear = $node;
}

function DeLinkQueue(LinkQueue &$queue) {
    if ($queue->first == $queue->rear) {
        return false;
    }

    $node = $queue->first->next;
    $v = $node->data;

    $queue->first->next = $node->next;
    if ($queue->rear == $node) {
        $queue->rear = $queue->first;
    }

    return $v;
}
